package com.dubious.interview.hashtable;

import java.lang.UnsupportedOperationException;

public class HashTable<S extends Object, T extends Object> {
    
    public static final int DEFAULT_BUCKETS_INITIAL_SIZE = 10;
    public static final double LOAD_FACTOR = 0.7;
    public static final int BUCKET_ARRAY_INITIAL_SIZE = 2;
    
    private Entry[][] currentBuckets;
    private int size;
    
    public HashTable()
    {
        currentBuckets = new Entry[DEFAULT_BUCKETS_INITIAL_SIZE][];
        size = 0;
    }
    
    public void put(S key, T value)
    {
        if(put(currentBuckets, key, value))
        {
            size++;
        }
        
        if(size > currentBuckets.length * LOAD_FACTOR)
        {
            // have reached a threshold that requires us to rebuild the hash table
            currentBuckets = rebuildBuckets(currentBuckets);
        }
    }
    
    public T get(S key)
    {
        return get(currentBuckets, key);
    }
    
    public void remove(S key)
    {   
        if(remove(currentBuckets, key))
        {
            size--;
        }  
    }
    
    public int size()
    {
        return size;
    }
    
    private boolean put(Entry[][] buckets, S key, T value)
    {
        // determine which bucket is appropriate for this key
        int bucketsPosition = getBucketsPosition(buckets, key);
        
        // create bucket array if necessary
        if(buckets[bucketsPosition] == null)
        {
            buckets[bucketsPosition] = new Entry[BUCKET_ARRAY_INITIAL_SIZE];
        }
        
        // expand bucket array if necessary
        if(buckets[bucketsPosition][buckets[bucketsPosition].length - 1] != null)
        {
            buckets[bucketsPosition] = expandBucketArray(buckets[bucketsPosition]);
        }
        
        for(int i = 0; i < buckets[bucketsPosition].length; i++)
        {
            Entry<S, T> entry = buckets[bucketsPosition][i];
            if(entry == null)
            {
                // append the entry to the end of the bucket array
                buckets[bucketsPosition][i] = new Entry(key, value);
                return true;
            } else if(entry.key.equals(key))
            {
                // found existing entry, replace it
                buckets[bucketsPosition][i] = new Entry(key, value);
                return false;
            }
        }
        
        throw new RuntimeException("How Did This happen?");
    }
    
    public T get(Entry[][] buckets, S key)
    {
        // determine which bucket is appropriate for this key
        int bucketsPosition = getBucketsPosition(buckets, key);
        
        // if bucket array does not exist, return null
        if(buckets[bucketsPosition] == null)
        {
            return null;
        }
        
        // search bucket array for given key
        for(int i = 0; i<buckets[bucketsPosition].length; i++)
        {
            Entry<S,T> entry = buckets[bucketsPosition][i];
            // found, return value
            if(entry != null && entry.key.equals(key))
            {
                return entry.value;
            }
        }
        
        // bucket not found, return null
        return null;
    }
    
    public boolean remove(Entry[][] buckets, S key)
    {   
        // determine which bucket is appropriate for this key
        int bucketsPosition = getBucketsPosition(buckets, key);
        
        // if bucket array does not exist, nothing to do
        if(buckets[bucketsPosition] == null)
        {
            return false;
        }
        
        // search array for given key
        for(int i = 0; i < buckets[bucketsPosition].length; i++)
        {
            Entry<S, T> entry = buckets[bucketsPosition][i];
            if(entry != null && entry.key.equals(key)) 
            {
                // found, remove and adjust array
                removeFromBucketArray(buckets[bucketsPosition], i);
                return true;
            }
        }   
        
        return false;
    }
    
    private int getBucketsPosition(Entry[][] buckets, S key)
    {
        // calculate hash of key and mod it by the number of buckets
        // the remainder operation can return negative so must always return absolute value.
        return Math.abs(key.hashCode() % buckets.length);
    }
    
    private Entry[] expandBucketArray(Entry[] bucket)
    {
        Entry[] newBucket = new Entry[bucket.length * 2];
        System.arraycopy(bucket, 0, newBucket, 0, bucket.length);
        return newBucket;
    }
    
    private void removeFromBucketArray(Entry[] bucketArray, int position)
    {
        // null the element at the position to remove
        bucketArray[position] = null;
        
        // slide subsequent entries to the left to fill the gap
        for(int i = position; i < bucketArray.length - 1; i++)
        {
            if(bucketArray[i + 1] != null)
            {
                bucketArray[i] = bucketArray[i + 1];
                bucketArray[i + 1] = null;
            }
        }
    }
    
    private Entry<S,T>[][] rebuildBuckets(Entry<S,T>[][] originalBuckets)
    {
        Entry<S,T>[][] newBuckets = new Entry[originalBuckets.length * 2][];        
        
        for(Entry<S,T>[] bucketArray : originalBuckets)
        {
            if(bucketArray != null)
            {
                for(Entry<S,T> entry : bucketArray)
                {
                    if(entry != null)
                    {
                        put(newBuckets, entry.key, entry.value);
                    }
                }
            }
        }
        
        return newBuckets;
    }
    
    private class Entry<S, T> 
    {
        private S key;
        private T value;
        
        private Entry(S key, T value)
        {
            this.key = key;
            this.value = value;
        }
    }
}